Many computer and data base applications involve data having a multi-dimensional nature. For example, data in a spreadsheet is referenced with regard to the particular row and column in which the data appears. The same is applicable to video image data, physical object data, and hierarchical data base elements. Video image data is referenced with regard to the particular x and y coordinate location at which the image data is displayed. Physical object data is referenced with regard to x, y, z coordinates, often termed the real-world coordinates of the object. Hierarchical data base elements are referenced by their path in a multidimensional tree structure. Traditionally, the coordinates associated with the representation of the data are termed object coordinates, or virtual coordinates.
Conventional memory devices are structured with a unidimensional addressing scheme. That is, each data element within the memory is referenced by a unique, single dimensioned, address. Storing multi-dimensional data in a unidimensional memory requires a mapping from each multidimensional object coordinate to a corresponding unidimensional memory address. One such mapping of a multidimensional representation to a unidimensional address is a linear mapping, as shown in FIG. 1. The object space 100 comprises data elements, or picture elements (pixels), arranged in a two-dimensional address space. Each pixel is represented by its location in these two dimensions, as shown by P(0,0), P(1,0), etc. in FIG. 1. In the linear mapping shown in FIG. 1, each of the pixels in the first row, or line, of pixels is stored sequentially in the memory 110. The pixels of the second line, P(0,1), P(1,1), etc. are stored sequentially after the first line of pixels. In a linear mapping, a linear equation is applied to compute the memory address corresponding to each object coordinate. For example, in the mapping shown in FIG. 1, the memory address, A, is equal to x+1024*y, where x is the first pixel coordinate, and y is the second pixel coordinate. In a three dimensional, (x, y, z), system, the memory address is computed as A=z*K2+y*K1+x, where K1 is the range of x, and K2 is the product of the range of x times the range of y.
When a linear mapping scheme is utilized, the address corresponding to an object coordinate can be calculated relative to a previously computed address. For example, in the mapping of FIG. 1, where A=x+1024*y, the address of a pixel to the right of another is offset by 1 from the address of the other; the address of a pixel below another is offset by 1024 from the address of the other. Utilizing this linear address relationship, memory access techniques can be optimized to process this data. For example, to process pixels lying along a vertical line, each entity can be accessed by adding 1024 to the prior address, rather than computing the address of each entity directly, using the x+1024*y formula. In this manner, a single addition (+1024) is used to compute the next address, rather than a multiplication (1024* y) and an addition (+x). In a similar manner, data at any periodic interval can be quickly accessed.
Although the linear addressing scheme offers considerable computational advantages for determining a coordinate's associated memory address, it does have disadvantages. In a linear mapping scheme, there is a fixed "distance" in memory 110 between data elements that are "adjacent" to each other in the object space 100. That is, for example, each pixel separated by one line in the object space 100 is separated by M locations in the memory 110, where M is the length of the line. In FIG. 1, P(0, 1) is at memory address 1024, whereas it's vertically adjacent element P(0,0) is at memory address 0, a separation of 1024 locations in memory. In the three-dimensional case discussed above, a distance of K2 separates data elements in adjacent z coordinates in memory. In many systems, the "cost", in terms of access time or access difficulty, is directly related to the distance between data items in memory. Often, a "block" of memory is accessed in a single memory access operation. If the "successive" data element, in the object coordinate space, is not within the block of memory accessed, a subsequent access is required. For example, in FIG. 1, the processing of data elements in a left to right fashion will be efficient, because each accessed block will contain a multitude of the data elements desired, thereby reducing the number of accesses required. Conversely, the processing of data elements of FIG. 1 in a top to bottom fashion will be inefficient, because each accessed block will typically contain only one of the desired data elements, the next desired data element being located a substantial distance (1024 memory locations) away from the prior vertically adjacent data element.
The inefficiencies of linear memory access for multidimensional data structures can be particularly problematic. Multi-dimensional applications often process data in an "area" or "regional" scheme. For example, in image processing, individual data elements are often smoothed, wherein a data element's value is modified by the values of data elements adjacent, in the object space, to this data element. Such area dependent processing will be efficient for processing data elements in one dimension, but inefficient in the other dimension, if a linear addressing scheme is utilized. To optimize performance in area or regional processing schemes, a non-linear mapping of multidimensional data is utilized to allocate contiguous blocks of memory to areas or regions of the object space, as shown in FIG. 2. The object space is partitioned into sub-areas, or tiles, and the elements of each tile are stored in a contiguous block of memory.
In FIG. 2, the object space is partitioned into tiles 101, 102, etc. of 12 pixels, arranged in a 4.times.3 manner. The first tile 101 comprises the data elements within the bounds between P(0,0) and P(3,2); the second tile 102 comprises the data elements within the bounds between P(4,0) and P(7,2); etc. As shown, the mapping of the first tile 101 is as follows: the first four pixels (P(0,0)-P(3,0)) are stored in the first four memory locations (memory address 0-3); the four pixels from the line below (P(0,1)-P(3,1)) are stored in the next four memory locations (memory address 4-7); the four pixels from the next line below (P(0,2)-P(3,2)) are stored in the next four memory locations (8-11). Thus, the first 12 memory locations contain the data elements of the first 4.times.3 tile 101. The second tile 102 is mapped in the next 12 memory locations in the same manner: pixels P(4,0)-P(7,0) are stored in the next four memory locations (12-15); pixels P(4,1)-P(7, 1) are stored next (16-19); etc. In this non-linear addressing scheme, pixels that are in proximity to each other in either dimension in the object space are generally close to each other in memory space, as compared to a linear addressing scheme.
A disadvantage of tiling, however, is that the non-linear mapping does not provide for the relative memory access technique discussed above. Because the mapping is non-linear, the relationship between the addresses of the data elements is not merely additive, as in the linear mapping scheme. That is, for example, the determination of an address corresponding to a data element adjacent to another data element is not merely effected by the addition of a constant, as in a linear addressing scheme, discussed above. Conventional memory access techniques for non-linear mappings require the direct computation of each memory address from the object coordinates. In FIG. 2, for example, P(0,2) is 4 memory locations beyond P(0,1), whereas P(0,3) is 3064 memory locations beyond P(0,2). Determining the address of every Nth data element cannot be effected by merely adding N*k to each preceding address, as in the linear addressing scheme. Conventionally, determining the memory address of P(0,3), and in general all coordinates in a non-linear mapping, requires a direct computation, based upon the object coordinate, rather than a relative computation, based on a previously computed address. Because the address of each coordinate in a non-linear mapping must be computed directly, the savings achieved by the determination of an address from a previously computed address, as in the linear addressing scheme, are not realized in a conventional non-linear mapping scheme.
Therefore, a need exists for a method and apparatus that provides the regional and area processing benefits of non-linear mapping, as well as the memory access benefits of linear mapping.